{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# N皇后问题及单机求解方法"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 多机数据处理: 课程第三部分主要内容，包含并行N皇后问题求解、多机整数统计（平均数/中位数）和多机高频词统计三个专题\n",
    "- 代码位置: 位于muduo-protorpc项目而非muduo主项目，使用基于Protocol Buffer的RPC实现\n",
    "- 课程来源: 内容改编自知乎高赞回答《Linux C++服务器端这条线怎么走？》中的两个练手题目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Plan for part III"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Parallel N-queens puzzle\n",
    "- Mean and median across machines\n",
    "- Most frequent queries\n",
    "- Code location\n",
    "  - https://github.com/chenshuo/muduo-protorpc\n",
    "- https://www.zhihu.com/question/22608820/answer/21968467"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 专题划分:\n",
    "  - 第一讲：并行N皇后问题求解（本讲）\n",
    "  - 第二讲：多机整数统计（平均数/中位数）\n",
    "  - 第三讲：多机高频词统计\n",
    "- 实验目标:\n",
    "  - 使用10台8核机器求解19/20皇后问题\n",
    "  - 支持异构机器负载均衡（附加题）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Agenda"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## N-皇后问题的多机并行求解\n",
    "\n",
    "利用多台机器求出 N 皇后问题有多少个解。  \n",
    "（注意目前的世界纪录是 N = 26，[A000170 - OEIS](http://oeis.org/A000170)）\n",
    "\n",
    "1. 8 皇后问题在单机上的运算时间是毫秒级，有 92 个解，编程实现之。\n",
    "2. 研究 N 皇后问题的并行算法，写一个单机多线程程序，争取达到线性加速比（以 CPU 核数计），再设计算法扩展到多机并行。\n",
    "3. 用 10 台 8 核的机器（一共 80 个 CPU cores），求解 19 皇后和 20 皇后问题，看看分别需要多少运行时间。你的方案能否平滑扩展到更多的机器？\n",
    "4. *(附加题)* 如果这 10 台机器的型号不一，有 8 核也有 16 核，有旧 CPU 也有更快的新 CPU，你该采用何种负载均衡策略，以求缩短求解时间？（至少比 plain round-robin 算法要好）\n",
    "\n",
    "| N   | Solutions   |\n",
    "|-----|-------------|\n",
    "| 8   | 92          |\n",
    "| 9   | 352         |\n",
    "| 10  | 724         |\n",
    "| 11  | 2680        |\n",
    "| 12  | 14200       |\n",
    "| 13  | 73712       |\n",
    "| 14  | 365596      |\n",
    "| 15  | 2279184     |\n",
    "| 16  | 14772512    |\n",
    "\n",
    "- **Answers:** [OEIS A000170](http://oeis.org/A000170)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "问题定义\n",
    "\n",
    "- 基本规则: 在$N \\times N$棋盘放置N个皇后，要求任意两个皇后不在同一行、列或对角线\n",
    "- 求解目标: 统计合法布局的数量（不需输出具体解）\n",
    "- 世界纪录: 当前最大解算规模为N=26（OEIS序列A000170）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# N-queens puzzle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "|   | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |\n",
    "|---|---|---|---|---|---|---|---|---|\n",
    "| row 0 |   |   |   |   |   |   |   |   |\n",
    "| row 1 |   |   |   |   |   |   |   |   |\n",
    "| row 2 |   |   |   |   |   |   |   |   |\n",
    "| row 3 |   |   |   |   |   |   |   |   |\n",
    "| row 4 |   |   |   |   |   |   |   |   |\n",
    "| row 5 |   |   |   |   |   |   |   |   |\n",
    "| row 6 |   |   |   |   |   |   |   |   |\n",
    "| row 7 |   |   |   |   |   |   |   |   |\n",
    "\n",
    "- `int rows[N];`\n",
    "- `rows[i]` is position (column) of Q in *i*-th row\n",
    "\n",
    "<br/>\n",
    "\n",
    "|   | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |\n",
    "|---|---|---|---|---|---|---|---|---|\n",
    "| row 0 | Q |   |   |   |   |   |   |   |\n",
    "| row 1 |   |   |   |   | Q |   |   |   |\n",
    "| row 2 |   |   |   |   |   |   |   | Q |\n",
    "| row 3 |   |   |   |   |   | Q |   |   |\n",
    "| row 4 |   |   | Q |   |   |   |   |   |\n",
    "| row 5 |   |   |   |   |   |   | Q |   |\n",
    "| row 6 |   | Q |   |   |   |   |   |   |\n",
    "| row 7 |   |   |   | Q |   |   |   |   |\n",
    "\n",
    "`[0, 4, 7, 5, 2, 6, 1, 3]`\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "问题规则说明\n",
    "\n",
    "- 攻击范围: 皇后可攻击同行、同列及两个对角线方向（共8个方向）\n",
    "- 约束条件:\n",
    "  - 每行必须且只能放置一个皇后\n",
    "  - 每列必须且只能放置一个皇后\n",
    "  - 每条对角线和反对角线最多一个皇后"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "状态表示方法\n",
    "\n",
    "- 一维数组表示: 使用长度为N的数组`rows[]`，其中`rows[i]`表示第`i`行皇后所在的列号\n",
    "- 示例解析: 图示解对应的数组为`[0,4,7,5,2,6,1,3]`，表示：\n",
    "  - 第0行皇后在第0列\n",
    "  - 第1行皇后在第4列\n",
    "  - 第2行皇后在第7列..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# N-queen by permutation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- A solution is permutation of first **N non-negative integers**\n",
    "- https://github.com/chenshuo/recipes/blob/master/python/nqueens.py\n",
    "- https://code.activestate.com/recipes/576647-eight-queens-six-lines/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [],
   "source": [
    "from itertools import permutations\n",
    "\n",
    "N = 8\n",
    "for rows in permutations(range(N)):\n",
    "    if (N == len(set(rows[i] - i for i in range(N)))   # Diagonal\n",
    "        == len(set(rows[i] + i for i in range(N)))):  # Anti-diagonal\n",
    "        print(rows)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> set集合中没有重复的元素; 主对角线方向是 斜率=1 的直线 (y = x + c), c就是棋盘坐标偏移。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Diagonal and Anti-Diagonal"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Diagonal (column - row)\n",
    "\n",
    "|   | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |\n",
    "|---|---|---|---|---|---|---|---|---|\n",
    "| row 0 | 0  | 1  | 2  | 3  | 4  | 5  | 6  | 7  |\n",
    "| row 1 | -1 | 0  | 1  | 2  | 3  | 4  | 5  | 6  |\n",
    "| row 2 | -2 | -1 | 0  | 1  | 2  | 3  | 4  | 5  |\n",
    "| row 3 | -3 | -2 | -1 | 0  | 1  | 2  | 3  | 4  |\n",
    "| row 4 | -4 | -3 | -2 | -1 | 0  | 1  | 2  | 3  |\n",
    "| row 5 | -5 | -4 | -3 | -2 | -1 | 0  | 1  | 2  |\n",
    "| row 6 | -6 | -5 | -4 | -3 | -2 | -1 | 0  | 1  |\n",
    "| row 7 | -7 | -6 | -5 | -4 | -3 | -2 | -1 | 0  |\n",
    "\n",
    "**Formula:**  \n",
    "`Diagonal = column - row`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Anti-Diagonal (column + row)\n",
    "\n",
    "|   | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |\n",
    "|---|---|---|---|---|---|---|---|---|\n",
    "| row 0 | 0  | 1  | 2  | 3  | 4  | 5  | 6  | 7  |\n",
    "| row 1 | 1  | 2  | 3  | 4  | 5  | 6  | 7  | 8  |\n",
    "| row 2 | 2  | 3  | 4  | 5  | 6  | 7  | 8  | 9  |\n",
    "| row 3 | 3  | 4  | 5  | 6  | 7  | 8  | 9  | 10 |\n",
    "| row 4 | 4  | 5  | 6  | 7  | 8  | 9  | 10 | 11 |\n",
    "| row 5 | 5  | 6  | 7  | 8  | 9  | 10 | 11 | 12 |\n",
    "| row 6 | 6  | 7  | 8  | 9  | 10 | 11 | 12 | 13 |\n",
    "| row 7 | 7  | 8  | 9  | 10 | 11 | 12 | 13 | 14 |\n",
    "\n",
    "**Formula:**  \n",
    "`Anti-diagonal = column + row`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 全排列解法"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 核心思想: 解空间是前N个非负整数的排列，使用Python的itertools.permutations生成\n",
    "- 验证方法:\n",
    "  - 对角线检查：`len(set(rows[i]-i for i in range(N))) == N`\n",
    "  - 反对角线检查：`len(set(rows[i]+i for i in range(N))) == N`\n",
    "- 效率问题: 需要验证所有N!种排列（如N=8时要验证40320种），选中率仅约0.25%"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# N-queens by backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Brute force enumeration is wasteful and slow, **8! = 40 320**\n",
    "  - [https://en.wikipedia.org/wiki/Backtracking](https://en.wikipedia.org/wiki/Backtracking)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 回溯法解法"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "回溯法原理\n",
    "\n",
    "- 基本流程: 逐行尝试放置皇后，遇到冲突则回溯到上一行调整位置\n",
    "- 优势: 通过剪枝避免无效搜索（如发现第3行无合法位置时立即回溯，无需继续尝试4-7行）\n",
    "- 对比全排列: 显著减少搜索空间，避免验证明显无效的排列组合"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> https://blog.csdn.net/lishuhuakai/article/details/60147128"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "位运算优化\n",
    "\n",
    "- 状态跟踪:\n",
    "  - `columns`: 记录已被占用的列\n",
    "  - `diagnoal`: 记录对角线方向限制\n",
    "  - `antidiagnoal`: 记录反对角线方向限制\n",
    "- 关键操作:\n",
    "  - 可用位置计算：`avail = ~(columns[row] | diagnoal[row] | antidiagnoal[row])`\n",
    "  - 位置提取：`_builtin_ctz(avail)`获取最低有效位1的位置\n",
    "  - 状态更新：\n",
    "- 性能优势: 通过位操作实现快速状态转移，单次操作时间复杂度接近$O(1)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 代码讲解"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**问题**：在 `N×N` 棋盘上放置 N 个皇后，使得同一行、列、对角线都不冲突。\n",
    "\n",
    "**解法**：逐行放置，每次用位掩码判断安全位置，递归搜索。\n",
    "\n",
    "**优化**：\n",
    "\n",
    "1. 使用 **位掩码 (bitmask)**，节省空间和加速判断。\n",
    "2. 使用 `__builtin_ctz` 找到最低位的 1 → 快速获取下一个可用位置。\n",
    "3. 用 **对称性**：只需搜索一半列，再乘 2；如果 N 为奇数，则加上中间列。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "// https://github.com/chenshuo/recipes/blob/master/puzzle/nqueens_opt.cc\n",
    "\n",
    "#include <algorithm>\n",
    "#include <vector>\n",
    "\n",
    "#include <assert.h>\n",
    "#include <stdio.h>\n",
    "#include <stdint.h>\n",
    "#include <stdlib.h>\n",
    "#include <strings.h>\n",
    "#include <sys/time.h>\n",
    "\n",
    "// 获取当前时间（秒），用于计时\n",
    "double now()\n",
    "{\n",
    "  struct timeval tv;\n",
    "  gettimeofday(&tv, NULL);\n",
    "  return tv.tv_sec + tv.tv_usec / 1000000.0;\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "struct BackTracking\n",
    "{\n",
    "  const static int kMaxQueens = 20; // 支持的最大棋盘大小\n",
    "\n",
    "  const int N;         // N 皇后中的 N\n",
    "  int64_t count;       // 用于统计解的个数\n",
    "  const uint32_t sentinel; // 1 << N，用来限制列索引范围\n",
    "\n",
    "  // 每一行存储对应的列/对角线占用情况，使用 bitmask\n",
    "  uint32_t columns[kMaxQueens];      // 列占用（竖直）\n",
    "  uint32_t diagnoal[kMaxQueens];     // 主对角线占用 (col - row) 方向 ↘\n",
    "  uint32_t antidiagnoal[kMaxQueens]; // 反对角线占用 (col + row) 方向 ↙\n",
    "\n",
    "  // 构造函数，初始化棋盘\n",
    "  BackTracking(int nqueens)\n",
    "      : N(nqueens), count(0), sentinel(1 << N)\n",
    "  {\n",
    "    assert(0 < N && N <= kMaxQueens);\n",
    "    bzero(columns, sizeof columns);       // 全部清零\n",
    "    bzero(diagnoal, sizeof diagnoal);\n",
    "    bzero(antidiagnoal, sizeof antidiagnoal);\n",
    "  }\n",
    "\n",
    "  // 回溯搜索，从 row 行开始放置皇后\n",
    "  void search(const int row)\n",
    "  {\n",
    "    // 计算当前行不能放的位置（已被列、主对角线、反对角线占用）\n",
    "    uint32_t avail = columns[row] | diagnoal[row] | antidiagnoal[row];\n",
    "    // avail = 1 表示占用，~avail 得到 1 表示可用的列\n",
    "    avail = ~avail;\n",
    "\n",
    "    // 枚举当前行的所有可放列（依次取最低位 1）\n",
    "    while (avail) {\n",
    "      int i = __builtin_ctz(avail); // 找出最低位 1 的下标 (最低列可用)\n",
    "      if (i >= N) {\n",
    "        break; // 超出棋盘范围\n",
    "      }\n",
    "\n",
    "      if (row == N - 1) {\n",
    "        // 已经放到最后一行，说明找到一个合法解\n",
    "        ++count;\n",
    "      } else {\n",
    "        const uint32_t m = 1 << i; // 当前列的掩码\n",
    "        // 更新下一行的列/对角线占用情况\n",
    "        columns[row+1] = columns[row] | m;\n",
    "        // 主对角线在下一行右移 1，因为斜率=1\n",
    "        diagnoal[row+1] = (diagnoal[row] | m) >> 1;\n",
    "        // 反对角线在下一行左移 1，因为斜率=-1\n",
    "        antidiagnoal[row+1] = (antidiagnoal[row] | m) << 1;\n",
    "        // 递归搜索下一行\n",
    "        search(row+1);\n",
    "      }\n",
    "\n",
    "      // 去掉当前使用的最低位 1，继续尝试下一个列位置\n",
    "      avail &= avail-1;\n",
    "    }\n",
    "  }\n",
    "};"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "// 把第一个皇后放在第 i 列，然后继续回溯\n",
    "int64_t backtrackingsub(int N, int i)\n",
    "{\n",
    "    const int row = 0;        // 第一行\n",
    "    const uint32_t m = 1 << i;// 第 i 列\n",
    "    BackTracking bt(N);\n",
    "\n",
    "    // 初始化第二行的列/对角线/反对角线信息\n",
    "    bt.columns[row+1] = m;\n",
    "    bt.diagnoal[row+1] = m >> 1;\n",
    "    bt.antidiagnoal[row+1] = m << 1;\n",
    "\n",
    "    // 从第 1 行开始递归（第 0 行已放）\n",
    "    bt.search(row+1);\n",
    "    return bt.count;\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "// 使用对称性优化的主入口\n",
    "int backtracking(int N)\n",
    "{\n",
    "  int64_t total = 0;\n",
    "  // 只搜索一半（左半部分），因为左右对称\n",
    "  for (int i = 0; i < N/2; ++i) {\n",
    "    total += backtrackingsub(N, i);\n",
    "  }\n",
    "  total *= 2; // 左右镜像解\n",
    "\n",
    "  // N 为奇数时，中间列的摆放需要单独算一次\n",
    "  if (N % 2 == 1) {\n",
    "    total += backtrackingsub(N, N/2);\n",
    "  }\n",
    "  return total;\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "92 solutions of 8 queens puzzle.\n",
      "0.000027 seconds.\n"
     ]
    }
   ],
   "source": [
    "{\n",
    "  // int nqueens = argc > 1 ? atoi(argv[1]) : 8;\n",
    "  int nqueens = 8;\n",
    "  double start = now();\n",
    "  int64_t solutions = backtracking(nqueens);\n",
    "  double end = now();\n",
    "  printf(\"%ld solutions of %d queens puzzle.\\n\", solutions, nqueens);\n",
    "  printf(\"%f seconds.\\n\", end - start);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Parallel N-queens by setting first row"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "|   | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |\n",
    "|---|---|---|---|---|---|---|---|---|\n",
    "| row 0 | **4** | **8** | **16** | **18** |   |   |   |   |\n",
    "| row 1 |   |   |   |   |   |   |   |   |\n",
    "| row 2 |   |   |   |   |   |   |   |   |\n",
    "| row 3 |   |   |   |   |   |   |   |   |\n",
    "| row 4 |   |   |   |   |   |   |   |   |\n",
    "| row 5 |   |   |   |   |   |   |   |   |\n",
    "| row 6 |   |   |   |   |   |   |   |   |\n",
    "| row 7 |   |   |   |   |   |   |   |   |\n",
    "\n",
    "- (4 + 8 + 16 + 18) * 2 = 92"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "|   | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |\n",
    "|---|---|---|---|---|---|---|---|---|---|\n",
    "| row 0 | **28** | **30** | **47** | **44** | **54** |   |   |   |   |\n",
    "| row 1 |    |    |    |    |    |   |   |   |   |\n",
    "| row 2 |    |    |    |    |    |   |   |   |   |\n",
    "| row 3 |    |    |    |    |    |   |   |   |   |\n",
    "| row 4 |    |    |    |    |    |   |   |   |   |\n",
    "| row 5 |    |    |    |    |    |   |   |   |   |\n",
    "| row 6 |    |    |    |    |    |   |   |   |   |\n",
    "| row 7 |    |    |    |    |    |   |   |   |   |\n",
    "| row 8 |    |    |    |    |    |   |   |   |   |\n",
    "\n",
    "- (28 + 30 + 47 + 44) * 2 + 54 = 352"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- For `N`, use `⌈N/2⌉` cores"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "基本并行思路\n",
    "- 固定首行法：通过固定第一行皇后的位置（如第0列），计算剩余行的可能解数量，再依次右移计算其他位置，最后汇总结果\n",
    "- 对称性优化：利用棋盘对称性，只需计算前$n/2$个位置的结果，最后乘以2（如8皇后问题总解数92=(4+8+16+18)×2）\n",
    "- 并行度限制：最大可用CPU核数为$\\lceil n/2 \\rceil$（如16皇后问题最多使用8核）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "奇数皇后处理\n",
    "- 中间列处理：当n为奇数时（如9皇后），中间列（第4列）无对称位置，需单独计算\n",
    "- 计算公式：前$\\lfloor n/2 \\rfloor$列结果×2 + 中间列结果（如9皇后总解数352=前4列和×2 + 中间列结果）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Increase parallelism by setting first two rows"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- $N \\lceil N/2 \\rceil$ sub problems:\n",
    "  - First row = 0, second row = 0..9\n",
    "  - First row = 1, second row = 0..9\n",
    "  - ...\n",
    "  - First row = 4, second row = 0..9\n",
    "  - Some sub problems are trivial"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "|       | 0      | 1    | 2     | 3      | 4     | 5      | 6      | 7      | 8     | 9     |\n",
    "| ----- | ------ | ---- | ----- | ------ | ----- | ------ | ------ | ------ | ----- | ----- |\n",
    "| row 0 | **64** |      |       |        |       |        |        |        |       |       |\n",
    "| row 1 | 0      | 0    | **4** | **11** | **6** | **13** | **10** | **13** | **5** | **2** |\n",
    "| row 2 |        |      |       |        |       |        |        |        |       |       |\n",
    "| row 3 |        |      |       |        |       |        |        |        |       |       |\n",
    "| row 4 |        |      |       |        |       |        |        |        |       |       |\n",
    "| row 5 |        |      |       |        |       |        |        |        |       |       |\n",
    "| row 6 |        |      |       |        |       |        |        |        |       |       |\n",
    "| row 7 |        |      |       |        |       |        |        |        |       |       |\n",
    "| row 8 |        |      |       |        |       |        |        |        |       |       |\n",
    "| row 9 |        |      |       |        |       |        |        |        |       |       |\n",
    "\n",
    "N = 10, solutions = 724"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "增加并行度方法\n",
    "- 两行固定法：同时固定前两行皇后位置，将问题分解为$N×\\lceil N/2 \\rceil$个子问题（如10皇后问题可拆分为50个计算任务）\n",
    "- 无效任务处理：部分子问题可快速判定无解（如第一行第0列时，第二行第0、1列必然冲突）\n",
    "- 性能提升：虽然总计算量不变，但并行度提高可缩短用户等待时间（如16皇后问题可扩展至128个子任务）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "sql"
    }
   },
   "outputs": [],
   "source": [
    "CREATE TABLE Result\n",
    "(`firstrow` int, `secondrow` int, `count` int);\n",
    "\n",
    "INSERT INTO Result\n",
    "(`firstrow`, `secondrow`, `count`)\n",
    "VALUES\n",
    "(0, 0, 0),\n",
    "(0, 1, 0),\n",
    "(0, 2, 4),\n",
    "(0, 3, 11),\n",
    "(0, 4, 6),\n",
    "(1, 0, 0),\n",
    "(1, 3, 5),\n",
    "(1, 4, 7);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "sql"
    }
   },
   "outputs": [],
   "source": [
    "SELECT firstrow, SUM(`count`)\n",
    "FROM result\n",
    "GROUP BY firstrow;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- [连接](https://sqliteonline.com/#sqltext=%23url-sqlite%3Ddb-sqlite%0D%0A%23tab-name%3DSQLite%0D%0ACREATE%20TABLE%20Result%0A(%60firstrow%60%20int%2C%20%60secondrow%60%20int%2C%20%60count%60%20int)%3B%0A%0AINSERT%20INTO%20Result%0A(%60firstrow%60%2C%20%60secondrow%60%2C%20%60count%60)%0AVALUES%0A(0%2C%200%2C%200)%2C%0A(0%2C%201%2C%200)%2C%0A(0%2C%202%2C%204)%2C%0A(0%2C%203%2C%2011)%2C%0A(0%2C%204%2C%206)%2C%0A(1%2C%200%2C%200)%2C%0A(1%2C%203%2C%205)%2C%0A(1%2C%204%2C%207)%3B%0A%0ASELECT%20firstrow%2C%20SUM(%60count%60)%0AFROM%20result%0AGROUP%20BY%20firstrow%3B)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 数据结构：建立包含firstrow、secondrow、count三列的结果表\n",
    "- 聚合查询：使用`SELECT firstrow, SUM(count) FROM result GROUP BY firstrow`实现分组求和\n",
    "- 实际验证：示例中第0行汇总21种解，第1行汇总12种解"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# N-queens by Map Reducing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- **Map** `(first_row, second_row)` → `(first_row, count)`\n",
    "- **Shuffle** `(first_row, [count₀, count₁, count₂, …])`\n",
    "- **Reduce** `(first_row, Σ countᵢ)` -- *IntSumReducer*\n",
    "- **Finally**, calculate total count"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Map阶段处理\n",
    "- 键值设计：Map输入为`(first_row, second_row)`对，输出为`(first_row, count)`键值对\n",
    "- 独立计算：每个子问题可分配到不同计算节点并行处理"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Reduce阶段\n",
    "- Shuffle过程：框架自动将相同`first_row`的`count`值聚合成数组\n",
    "- 求和归约：使用`IntSumReducer`（或`LongSumReducer`）对同`key`的count值求和\n",
    "- 最终计算：Reduce结果需结合对称性计算总解数（与基本并行算法最后步骤相同）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Remote Procedure Call (RPC)\n",
    "\n",
    "- https://en.wikipedia.org/wiki/Remote_procedure_call"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![10.1](./images/10.1.jpg)\n",
    "\n",
    "- The components of the system, and their interactions for a simple call"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "远程过程调用的组件及其交互\n",
    "- 基本原理: 将本地调用过程拆解后分布到多台机器执行，核心思想是让远程调用看起来像本地调用\n",
    "- 调用流程:\n",
    "  - 调用方: 用户程序发起本地调用→存根(stub)打包参数→RPC运行时发送网络包\n",
    "  - 被调用方: RPC接收消息→服务存根解包→调用实际函数→打包结果返回\n",
    "  - 接口定义: 在调用方和被调用方分别定义接口，确保参数和返回值的格式一致\n",
    "- 阻塞特性: 1984年实现的是阻塞调用，调用方会等待结果返回后才继续执行\n",
    "- 跨机器透明性: 中间网络传输细节对调用双方透明，就像在本地执行一样"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- **Implementing remote procedure calls**\n",
    "  - Andrew Birrell and Bruce Nelson, 1984\n",
    "- **Foundation of building distributed system**\n",
    "  - Defined system interfaces as RPC services in **IDL (.proto)**\n",
    "- **Examples**\n",
    "  - Sun RPC (C, for **NFS**), **XDR** as the **data format**\n",
    "  - **gRPC**, Thrift, SOAP, Java RMI, .NET Remoting/WCF, ICE, CORBA\n",
    "  - [muduo-protorpc](https://github.com/chenshuo/muduo-protorpc) for C++, Java and Go\n",
    "- **References**\n",
    "  - https://en.wikipedia.org/wiki/Remote_procedure_call"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 核心作用: 用机器可读的代码形式定义接口，避免依赖人工阅读文档\n",
    "- 与COM区别: 强调是通用概念(Interface Definition Language)，不是微软的COM技术\n",
    "- 优势:\n",
    "  - 可自动生成存根代码\n",
    "  - 提高接口定义的精确性和一致性\n",
    "  - 支持跨语言调用"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "谷歌的Protocol Buffer\n",
    "\n",
    "- 文件格式: 使用`.proto`后缀文件定义接口\n",
    "- 设计特点:\n",
    "  - 每个RPC调用只接受一个Protocol Buffer消息作为参数\n",
    "  - 返回也只有一个Protocol Buffer消息\n",
    "- 版本兼容:\n",
    "  - 通过消息字段扩展实现前后兼容\n",
    "  - 避免直接修改参数列表导致的版本冲突\n",
    "- 字段标注:\n",
    "  - required已被弃用(示例中仍使用)\n",
    "  - 推荐所有字段设为optional保证兼容性"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "RPC技术\n",
    "\n",
    "- 历史发展:\n",
    "  - 60年代提出概念\n",
    "  - 80年代Sun RPC(用于NFS)采用XDR数据格式\n",
    "  - 按时间逆序有多种实现方案\n",
    "- 核心要素: 共用数据格式决定RPC类型\n",
    "- 应用场景: 构建分布式系统的基础技术"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Google开源的gRPC\n",
    "\n",
    "- 发布时间: 2015-2016年开源\n",
    "- 关键优势:\n",
    "  - 跨语言支持(客户端和服务端可用不同语言)\n",
    "  - 便于测试(可用Python等脚本语言快速测试)\n",
    "- 设计理念: 不应限制特定编程语言"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "自定义RPC\n",
    "\n",
    "- 实现特点:\n",
    "  - 基于muduo-protorpc实现\n",
    "  - 支持C++/Java/Go三种语言\n",
    "  - 仅支持同步客户端\n",
    "- 教学价值:\n",
    "  - 代码量小(约几百行)\n",
    "  - 便于讲解实现原理和设计取舍\n",
    "  - 使用Protocol Buffer作为数据格式"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Define RPC Service in Protocol Buffers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- https://github.com/chenshuo/muduo-protorpc/blob/cpp11/examples/nqueens/nqueens.proto"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "properties"
    }
   },
   "outputs": [],
   "source": [
    "package nqueens;\n",
    "\n",
    "// option cc_generic_services = true;\n",
    "option java_generic_services = true;\n",
    "option py_generic_services = true;\n",
    "\n",
    "import \"muduo/protorpc2/rpc2.proto\";\n",
    "\n",
    "message SubProblemRequest {\n",
    "  required int32 nqueens = 1;\n",
    "  required int32 first_row = 2;\n",
    "  optional int32 second_row = 3 [default = -1];\n",
    "}\n",
    "\n",
    "message SubProblemResponse {\n",
    "  required int64 count = 1;\n",
    "  required double seconds = 2;\n",
    "}\n",
    "\n",
    "service NQueensService {\n",
    "  rpc Solve(SubProblemRequest) returns (SubProblemResponse);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 请求消息:\n",
    "  - nqueens: 皇后数量(required int32)\n",
    "  - first_row: 第一行位置(required int32)\n",
    "  - second_row: 第二行位置(optional int32, 默认-1)\n",
    "- 响应消息:\n",
    "  - count: 解的数量(required int64)\n",
    "  - seconds: 计算耗时(required double)\n",
    "- 设计考虑:\n",
    "  - 使用optional字段提高灵活性\n",
    "  - 默认值-1表示不指定第二行位置\n",
    "  - 包含计算时间用于性能分析"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 代码实现与运行实例"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- https://github.com/chenshuo/muduo-protorpc/tree/cpp11/examples/nqueens"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## server.cc"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "// https://github.com/chenshuo/muduo-protorpc/blob/cpp11/examples/nqueens/server.cc\n",
    "\n",
    "#include <examples/nqueens/nqueens.pb.h>\n",
    "\n",
    "#include <muduo/base/Logging.h>\n",
    "#include <muduo/base/ThreadPool.h>\n",
    "#include <muduo/net/EventLoop.h>\n",
    "#include <muduo/protorpc2/RpcServer.h>\n",
    "\n",
    "using namespace muduo;\n",
    "using namespace muduo::net;\n",
    "\n",
    "namespace nqueens\n",
    "{\n",
    "\n",
    "struct BackTracking\n",
    "{\n",
    "  const static int kMaxQueens = 20;\n",
    "\n",
    "  const int N;\n",
    "  int64_t count;\n",
    "  // bitmasks, 1 means occupied, all 0s initially\n",
    "  uint32_t columns[kMaxQueens];\n",
    "  uint32_t diagnoal[kMaxQueens];\n",
    "  uint32_t antidiagnoal[kMaxQueens];\n",
    "\n",
    "  BackTracking(int nqueens)\n",
    "      : N(nqueens), count(0)\n",
    "  {\n",
    "    assert(0 < N && N <= kMaxQueens);\n",
    "    bzero(columns, sizeof columns);\n",
    "    bzero(diagnoal, sizeof diagnoal);\n",
    "    bzero(antidiagnoal, sizeof antidiagnoal);\n",
    "  }\n",
    "\n",
    "  void search(const int row)\n",
    "  {\n",
    "    uint32_t avail = columns[row] | diagnoal[row] | antidiagnoal[row];\n",
    "    avail = ~avail;\n",
    "\n",
    "    while (avail) {\n",
    "      int i = __builtin_ctz(avail); // counting trailing zeros\n",
    "      if (i >= N) {\n",
    "        break;\n",
    "      }\n",
    "      if (row == N - 1) {\n",
    "        ++count;\n",
    "      } else {\n",
    "        const uint32_t mask = 1 << i;\n",
    "        columns[row+1] = columns[row] | mask;\n",
    "        diagnoal[row+1] = (diagnoal[row] | mask) >> 1;\n",
    "        antidiagnoal[row+1] = (antidiagnoal[row] | mask) << 1;\n",
    "        search(row+1);\n",
    "      }\n",
    "\n",
    "      avail &= avail-1;  // turn off last bit\n",
    "    }\n",
    "  }\n",
    "};\n",
    "\n",
    "int64_t backtrackingsub(int N, int first_row, int second_row)\n",
    "{\n",
    "  const uint32_t m0 = 1 << first_row;\n",
    "  BackTracking bt(N);\n",
    "  bt.columns[1] = m0;\n",
    "  bt.diagnoal[1] = m0 >> 1;\n",
    "  bt.antidiagnoal[1] = m0 << 1;\n",
    "\n",
    "  if (second_row >= 0)\n",
    "  {\n",
    "    const int row = 1;\n",
    "    const uint32_t m1 = 1 << second_row;\n",
    "    uint32_t avail = bt.columns[row] | bt.diagnoal[row] | bt.antidiagnoal[row];\n",
    "    avail = ~avail;\n",
    "    if (avail & m1)\n",
    "    {\n",
    "      bt.columns[row+1] = bt.columns[row] | m1;\n",
    "      bt.diagnoal[row+1] = (bt.diagnoal[row] | m1) >> 1;\n",
    "      bt.antidiagnoal[row+1] = (bt.antidiagnoal[row] | m1) << 1;\n",
    "      bt.search(row+1);\n",
    "      return bt.count;\n",
    "    }\n",
    "  }\n",
    "  else\n",
    "  {\n",
    "    bt.search(1);\n",
    "    return bt.count;\n",
    "  }\n",
    "  return 0;\n",
    "}\n",
    "\n",
    "class NQueensServiceImpl : public NQueensService\n",
    "{\n",
    " public:\n",
    "  NQueensServiceImpl(int threads)\n",
    "  {\n",
    "    pool_.start(threads);\n",
    "  }\n",
    "\n",
    "  void Solve(const ::nqueens::SubProblemRequestPtr& request,\n",
    "             const ::nqueens::SubProblemResponse* responsePrototype,\n",
    "             const RpcDoneCallback& done) override\n",
    "  {\n",
    "    LOG_INFO << \"NQueensServiceImpl::Solve \" << request->ShortDebugString();\n",
    "    pool_.run(std::bind(&NQueensServiceImpl::doSolve, request, done));\n",
    "  }\n",
    "\n",
    "\n",
    "  static void doSolve(const ::nqueens::SubProblemRequestPtr& request,\n",
    "                      const RpcDoneCallback& done)\n",
    "  {\n",
    "    Timestamp start(Timestamp::now());\n",
    "    int64_t count = backtrackingsub(request->nqueens(),\n",
    "                                    request->first_row(),\n",
    "                                    request->second_row());\n",
    "    SubProblemResponse response;\n",
    "    response.set_count(count);\n",
    "    response.set_seconds(timeDifference(Timestamp::now(), start));\n",
    "    done(&response);\n",
    "  }\n",
    "\n",
    " private:\n",
    "  muduo::ThreadPool pool_;\n",
    "};\n",
    "\n",
    "}\n",
    "\n",
    "int main(int argc, char* argv[])\n",
    "{\n",
    "  LOG_INFO << \"pid = \" << getpid();\n",
    "  EventLoop loop;\n",
    "  int threads = argc > 1 ? atoi(argv[1]) : 0;\n",
    "  nqueens::NQueensServiceImpl impl(threads);\n",
    "  int port = argc > 2 ? atoi(argv[2]) : 9352;\n",
    "  InetAddress listenAddr(static_cast<uint16_t>(port));\n",
    "  RpcServer server(&loop, listenAddr);\n",
    "  server.registerService(&impl);\n",
    "  server.start();\n",
    "  loop.loop();\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 算法实现：采用位运算优化的回溯算法，通过三个位掩码数组（columns、diagnoal、antidiagnoal）快速判断皇后位置冲突\n",
    "- 位运算技巧：\n",
    "  - 使用`builtin_ctz(avail)`计算尾随零数量快速定位可用位置\n",
    "  - `avail &= avail-1`关闭最后一位实现快速迭代\n",
    "  - 掩码更新规则：列掩码直接或运算，对角线掩码右移，反对角线掩码左移\n",
    "- 初始化约束：\n",
    "  - 最大皇后数限制`kMaxQueens=20`\n",
    "  - 构造函数中进行数组清零操作（bzero）\n",
    "- 搜索过程：\n",
    "  - 通过`avail = ~(columns[row] | diagnoal[row] | antidiagnoal[row])`获取可用位置\n",
    "  - 递归搜索直到最后一行（`row=N-1`）时计数\n",
    "- 线程池设计：\n",
    "  - 使用muduo库的`ThreadPool`实现异步处理\n",
    "  - `Solve`方法将任务提交到线程池，通过回调返回结果\n",
    "- 性能统计：\n",
    "  - 记录计算耗时（Timestamp差值）\n",
    "  - 响应包含解的数量和计算时间\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## client.cc"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "// https://github.com/chenshuo/muduo-protorpc/blob/cpp11/examples/nqueens/client.cc\n",
    "\n",
    "#include <examples/nqueens/nqueens.pb.h>\n",
    "\n",
    "#include <muduo/base/Logging.h>\n",
    "#include <muduo/net/EventLoop.h>\n",
    "#include <muduo/net/TcpClient.h>\n",
    "\n",
    "using namespace muduo;\n",
    "using namespace muduo::net;\n",
    "\n",
    "namespace nqueens\n",
    "{\n",
    "\n",
    "int g_got = 0;\n",
    "int64_t g_total = 0;\n",
    "\n",
    "void run(int N, NQueensService::Stub* stub, EventLoop* loop)\n",
    "{\n",
    "  LOG_INFO << \"N=\" << N;\n",
    "  for (int col = 0; col < (N+1)/2; ++col)\n",
    "  {\n",
    "    SubProblemRequest request;\n",
    "    request.set_nqueens(N);\n",
    "    request.set_first_row(col);\n",
    "    stub->Solve(request, [N, col, loop](const SubProblemResponsePtr& resp)\n",
    "      {\n",
    "        LOG_INFO << \"response for col=\" << col << \" : \" << resp->ShortDebugString();\n",
    "        if (N % 2 == 1 && col == N / 2)\n",
    "          g_total += resp->count();\n",
    "        else\n",
    "          g_total += 2*resp->count();\n",
    "\n",
    "        ++g_got;\n",
    "        if (g_got == (N+1)/2)\n",
    "        {\n",
    "          LOG_INFO << \"total: \" << g_total;\n",
    "          // TODO: disconnect\n",
    "        }\n",
    "      });\n",
    "  }\n",
    "}\n",
    "\n",
    "}\n",
    "\n",
    "int main(int argc, char* argv[])\n",
    "{\n",
    "  if (argc > 1)\n",
    "  {\n",
    "    int N = atoi(argv[1]);\n",
    "    const char* ip = argc > 2 ? argv[2] : \"127.0.0.1\";\n",
    "    int port = argc > 3 ? atoi(argv[3]) : 9352;\n",
    "    InetAddress serverAddr(ip, static_cast<uint16_t>(port));\n",
    "\n",
    "    EventLoop loop;\n",
    "    TcpClient client(&loop, serverAddr, \"NqueensClient\");\n",
    "    RpcChannel channel;\n",
    "    nqueens::NQueensService::Stub stub(&channel);\n",
    "\n",
    "    client.setConnectionCallback(\n",
    "      [N, &channel, &stub, &loop](const TcpConnectionPtr& conn) {\n",
    "        if (conn->connected())\n",
    "        {\n",
    "          channel.setConnection(conn);\n",
    "          run(N, &stub, &loop);  // Koenig lookup\n",
    "        }\n",
    "        else\n",
    "        {\n",
    "          channel.setConnection(TcpConnectionPtr());\n",
    "          loop.quit();\n",
    "        }\n",
    "      });\n",
    "\n",
    "    client.setMessageCallback(\n",
    "        std::bind(&RpcChannel::onMessage, &channel, _1, _2, _3));\n",
    "    client.connect();\n",
    "    loop.loop();\n",
    "    google::protobuf::ShutdownProtobufLibrary();\n",
    "  }\n",
    "  else\n",
    "  {\n",
    "    printf(\"Usage: %s N [host_ip [port]]\\n\", argv[0]);\n",
    "  }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 任务分发策略：\n",
    "  - 仅需计算前(N+1)/2列情况（利用对称性）\n",
    "  - 奇数N时中间列结果不加倍\n",
    "- 全局状态管理：\n",
    "  - 使用`g_total`累加结果\n",
    "  - `g_got`统计已完成任务数\n",
    "  - 全部完成后通过`loop->quit()`退出事件循环\n",
    "\n",
    "- 连接生命周期：\n",
    "  - 建立连接后设置`RpcChannel`\n",
    "  - 断开连接时清理`Channel`状态\n",
    "- 请求构造：\n",
    "  - 设置皇后数量`nqueens`\n",
    "  - 指定首行皇后位置`first_row`\n",
    "  - 可选指定次行位置`second_row`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 代码运行实例"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "服务端\n",
    "\n",
    "```shell\n",
    "bin/nqueens_server 2 # 线程池2个线程\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "客户端(python)\n",
    "\n",
    "```shell\n",
    "./nqueens_cli.sh 8 0\n",
    "```\n",
    "\n",
    "```shell\n",
    "./nqueens_cli.sh 8 1\n",
    "```\n",
    "\n",
    "```shell\n",
    "./nqueens_cli.sh 10 0\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "客户端(C++)\n",
    "\n",
    "```shell\n",
    "bin/nqueens_client 8\n",
    "```\n",
    "\n",
    "```shell\n",
    "bin/nqueens_client 10\n",
    "```\n",
    "\n",
    "```shell\n",
    "bin/nqueens_client 12\n",
    "```\n",
    "\n",
    "```shell\n",
    "bin/nqueens_client 14\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "服务端\n",
    "\n",
    "```shell\n",
    "bin/nqueens_server 4 # 线程池4个线程\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "客户端(C++)\n",
    "\n",
    "\n",
    "```shell\n",
    "bin/nqueens_client 14 # 乱序返回\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## client.go"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "go"
    }
   },
   "outputs": [],
   "source": [
    "// https://github.com/chenshuo/muduo-protorpc/blob/cpp11/examples/nqueens/go/nqueens-client/client.go\n",
    "\n",
    "package main\n",
    "\n",
    "import (\n",
    "\t\"fmt\"\n",
    "\tnqueens \"github.com/chenshuo/muduo-protorpc/examples/nqueens/go\"\n",
    "\t\"log\"\n",
    "\t\"net\"\n",
    "\t\"os\"\n",
    "\t\"strconv\"\n",
    ")\n",
    "\n",
    "var threshold = 14\n",
    "\n",
    "type Shard struct {\n",
    "\tfirst_row, second_row int32\n",
    "\tcount                 int64\n",
    "}\n",
    "\n",
    "func solve(solver nqueens.NQueensService, N, first_row int32, second_row *int32) int64 {\n",
    "\treq := new(nqueens.SubProblemRequest)\n",
    "\tresp := new(nqueens.SubProblemResponse)\n",
    "\treq.Nqueens = &N\n",
    "\treq.FirstRow = &first_row\n",
    "\treq.SecondRow = second_row\n",
    "\terr := solver.Solve(req, resp)\n",
    "\tif err == nil {\n",
    "\t\tlog.Print(req, resp)\n",
    "\t\treturn *resp.Count\n",
    "\t} else {\n",
    "\t\tlog.Print(err)\n",
    "\t}\n",
    "\treturn -1\n",
    "}\n",
    "\n",
    "func mapper(solver nqueens.NQueensService, N int) (result []Shard) {\n",
    "\tshards := 0\n",
    "\tch := make(chan Shard)\n",
    "\tfor i := 0; i < (N+1)/2; i++ {\n",
    "\t\tif N <= threshold {\n",
    "\t\t\tshards++\n",
    "\t\t\tgo func(first_row int32) {\n",
    "\t\t\t\tcount := solve(solver, int32(N), first_row, nil)\n",
    "\t\t\t\tch <- Shard{first_row, -1, count}\n",
    "\t\t\t}(int32(i))\n",
    "\t\t} else {\n",
    "\t\t\tfor j := 0; j < N; j++ {\n",
    "\t\t\t\tshards++\n",
    "\t\t\t\tgo func(first_row, second_row int32) {\n",
    "\t\t\t\t\tcount := solve(solver, int32(N), first_row, &second_row)\n",
    "\t\t\t\t\tch <- Shard{first_row, second_row, count}\n",
    "\t\t\t\t}(int32(i), int32(j))\n",
    "\t\t\t}\n",
    "\t\t}\n",
    "\t}\n",
    "\tfor i := 0; i < shards; i++ {\n",
    "\t\tresult = append(result, <-ch)\n",
    "\t}\n",
    "\treturn\n",
    "}\n",
    "\n",
    "func verify(N int, shards []Shard) {\n",
    "\tresults := map[int32][]int32{}\n",
    "\tfor _, shard := range shards {\n",
    "\t\tx := results[shard.first_row]\n",
    "\t\tresults[shard.first_row] = append(x, shard.second_row)\n",
    "\t}\n",
    "\n",
    "\t// log.Print(results)\n",
    "\t// TODO: verify shards\n",
    "}\n",
    "\n",
    "func reducer(N int, shards []Shard) int64 {\n",
    "\tresults := map[int]int64{}\n",
    "\n",
    "\tfor _, shard := range shards {\n",
    "\t\tresults[int(shard.first_row)] += shard.count\n",
    "\t}\n",
    "\tlog.Print(\"results = \", results)\n",
    "\n",
    "\tvar total int64\n",
    "\tfor i := 0; i < (N+1)/2; i++ {\n",
    "\t\tif N%2 == 1 && i == N/2 {\n",
    "\t\t\ttotal += results[i]\n",
    "\t\t} else {\n",
    "\t\t\ttotal += 2 * results[i]\n",
    "\t\t}\n",
    "\t}\n",
    "\treturn total\n",
    "}\n",
    "\n",
    "func main() {\n",
    "\tif len(os.Args) < 2 {\n",
    "\t\tfmt.Println(\"Usage: nqueens-client N\")\n",
    "\t\treturn\n",
    "\t}\n",
    "\n",
    "\tN, _ := strconv.Atoi(os.Args[1])\n",
    "\tconn, err := net.Dial(\"tcp\", \"localhost:9352\")\n",
    "\tif err != nil {\n",
    "\t\tlog.Fatal(err)\n",
    "\t}\n",
    "\n",
    "\tsolver := nqueens.NewNQueensServiceClient(conn)\n",
    "\tlog.Print(\"N = \", N)\n",
    "\tshards := mapper(solver, N)\n",
    "\tlog.Print(\"shards = \", shards)\n",
    "\tverify(N, shards)\n",
    "\tsolution := reducer(N, shards)\n",
    "\tlog.Print(\"solution = \", solution)\n",
    "\n",
    "\tsolver.Close()\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 纯代码, 不如AI讲解"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Server and clients, demo"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Not very typical, More like a **batch job**, not a serving job"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# RPC Balancer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 特点：演示的RPC服务属于批处理作业而非典型的在线请求响应模式\n",
    "- 实现差异：当前示例仅展示单机线程池实现，未体现多机并行处理能力\n",
    "- 技术展示：虽然使用了RPC技术，但主要用于演示跨进程调用而非分布式处理"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- https://github.com/chenshuo/muduo-protorpc/tree/cpp11/go/balancer\n",
    "- https://github.com/chenshuo/muduo/tree/master/examples/protobuf/rpcbalancer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "负载均衡器的作用\n",
    "\n",
    "- 核心功能：作为客户端与服务端之间的代理，接收请求后选择最优服务端转发\n",
    "- 工作流程：客户端连接负载均衡器→均衡器选择服务端→返回响应给客户端\n",
    "- 架构类型：属于反向代理模式，对客户端透明"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![10.2](./images/10.2.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "负载均衡器的实现\n",
    "\n",
    "- 实现版本：\n",
    "  - Go语言实现的通用负载均衡器\n",
    "  - 示例中包含两个变体：解析/不解析RPC消息\n",
    "- 优化方案：原始版通过已知消息ID偏移量直接操作，避免protobuf序列化开销\n",
    "- 单点风险：集中式负载均衡器存在单点故障风险（SPOF）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![10.3](./images/10.3.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "负载均衡策略\n",
    "\n",
    "1）stop with balance\n",
    "- 分布式方案：将均衡逻辑嵌入客户端存根(stub)，实现去中心化负载均衡\n",
    "- 连接管理：每个客户端直接连接多个服务端，自主进行路由选择\n",
    "\n",
    "2）客户端连接\n",
    "- 规模问题：当客户端(N)和服务端(M)数量较大时，全连接会产生N×M个连接\n",
    "- 示例：500客户端×500服务端=25万连接，超出单机承载能力\n",
    "\n",
    "3）两层负载均衡\n",
    "- 分层设计：\n",
    "  - 第一层：20个负载均衡器，每个连接20个服务端（共400服务端）\n",
    "  - 第二层：客户端连接20个均衡器\n",
    "- 优势：将连接数从N×M降至N×L（L为均衡器数量），示例中降至几百连接"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "负载均衡策略\n",
    "\n",
    " 1）轮盘方式\n",
    "- 适用场景：服务端配置均匀（如均为8核服务器）\n",
    "- 实现方式：按固定顺序循环分配请求（Round Robin）\n",
    "\n",
    " 2）处理能力代表成比例的放请求\n",
    "- 权重分配：根据服务器处理能力按比例分配请求量\n",
    "  - 示例：4核与8核服务器按1:2比例分配128个子问题\n",
    "- 前提条件：需要预先知晓各服务器配置信息\n",
    "\n",
    " 3）自适应过程\n",
    "- 动态学习：对于未知性能的服务器，通过持续请求进行能力评估\n",
    "- 适用限制：批处理作业因请求不持续，难以实现有效学习\n",
    "\n",
    " 4）选出pending response最少的服务器\n",
    "- 优选策略：选择当前待处理响应最少的服务器（书中第9章推荐方案）\n",
    "- 效果验证：在线服务场景下被证明为高效策略，能动态适应服务器负载变化"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "C++17",
   "language": "C++17",
   "name": "xcpp17"
  },
  "language_info": {
   "codemirror_mode": "text/x-c++src",
   "file_extension": ".cpp",
   "mimetype": "text/x-c++src",
   "name": "c++",
   "version": "17"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
